/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package org.osdtsystem.hierarchy;

import java.util.ArrayList;
import java.util.Collection;
import org.osdtsystem.dataset.Classification;
import org.osdtsystem.dataset.ClassificationEngine;
import org.osdtsystem.dataset.Dataset;
import org.osdtsystem.dataset.HierarchyView;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import org.osdtsystem.utils.Storage;

/**
 * A product hierarchy composed of other hierarchies. Each subhierarchy has
 * an associated level, denoted by level(k) for the kth subhierarchy, which
 * must be an integer. Given a class x=(x1,...,xn),
 * the direct subclasses of x are of the form (x1,...,x[k-1],xk',x[k+1],...,xn)
 * where xk' is a direct subclass of xk and where level(k) &geq; level(m) for
 * any m where xm is different from the top class. If a level is negative,
 * the corresponding component hierarchy is ignored and behaves as if the only 
 * class in the component hierarchy is the component top class.
 *
 * Hierarchies where all subhierarchies are on the same level are called
 * <i>single-level product hierarchies</i>. In these hierarchies, a class can be
 * generated from the top class by refining the components in any order.
 * Eg, we can create the class (x,y) by expanding (TOP,TOP) into (x,TOP) and
 * then (x,y), or we could expand (TOP,TOP) into (TOP,y) and then (x,y).
 *
 * Hierarchies where all subhierarchies are on different levels are called
 * <i>sequential product hierarchies</i>. In these hierarchies, there is a unique
 * order in which a class is constructed from the top class by refining the
 * components. Eg, if the first component has level 0 and the second level 1,
 * the only way to create the class (x,y) is by expanding (TOP,TOP) into
 * (x,TOP) and then (x,y). In contrast, (x,y) is not a subclass of (TOP,y)
 * because the x-component is at a lower level than the y-component.
 *
 * A sequential product hierarchy contains the same set of classes as the corresponding
 * general product hierarchy, but the hierarchy structure is much simpler.
 * In particular, if all the subhierarchies in the sequential product hierarchy are
 * tree hierarchies, then the sequential product hierarchy is a tree hierarchy as well.
 * In contrast, the corresponding product hierarchy would in general be a highly complex
 * poly-hierarchy.
 *
 * A general product hierarchy always contains a <code>subhierarchyOrdering</code> method,
 * which defines the order in which the subhierarchies in the hierarchy is processed.
 * This ordering is also used as the ordering for the sequential product hierarchy.

 * @author Martin Haulrich and Matthias Buch-Kromann
 */
public class ProductHierarchy extends AbstractHierarchy<ProductHClass> {
    final Hierarchy<?>[] hierarchies;
    private final int[] minLevels;
    private final int[] maxLevels;
    private int dimensions = 0;
    int[] componentOrdering;

    public static final String PRODUCTSEPARATOR = " x ";

    /**
     * Construct a new product hierarchy from a list of hierarchies.
     * @param storage the storage component
     * @param hierarchies the component hierarchies
     * @param minLevels the levels at which the component hierarchies are activated
     * @param maxLevels the levels at which the component hierarchies are deactivated again
     */
    public ProductHierarchy(Storage storage, Hierarchy<?>[] hierarchies, int[] minLevels, int[] maxLevels) {
        // Call super constructor
        super(ProductHClass.class, storage);

        // Create copy of hierarchies
        this.hierarchies = Arrays.copyOf(hierarchies, hierarchies.length);

        // Compute dimensions
        for (int i = 0; i < hierarchies.length; ++i)
            dimensions += hierarchies[i].dimensions();

        //  Store component ordering
        this.componentOrdering = new int[hierarchies.length];
        
        // Store levels
        if (minLevels == null) {
            // Assume all hierarchies are on level 0
            this.minLevels = new int[hierarchies.length];
            for (int i = 0; i < hierarchies.length; ++i)
                this.minLevels[i] = 0;
            this.maxLevels = this.minLevels;
        } else if (minLevels.length != hierarchies.length || maxLevels.length != hierarchies.length) {
            throw new IllegalArgumentException("Illegal number of levels in product " +
                    "hierarchy constructor: there are "
                    + hierarchies.length + " hierarchies, but "
                    + minLevels.length + " minLevels and "
                    + maxLevels.length + " maxLevels");
        } else {
            // Use levels provided by constructor
            this.minLevels = minLevels;
            this.maxLevels = maxLevels;
        }
    }

    public ProductHierarchy(Storage storage, Hierarchy<?>[] hierarchies) {
        this(storage, hierarchies, null, null);
    }

    @Override
    public int dimensions() {
        return dimensions;
    }

    public int components() {
        return hierarchies.length;
    }

    private Hierarchy<?> subhierarchy(int component) {
        return (component < 0 || component >= components())
            ? null : hierarchies[component];
    }

    public ProductHClass makeClass(HClass[] hclasses) {
        // Check component
        if (hclasses.length != components())
            throw new HierarchyRuntimeException2("Cannot make product class with component "
                    + components() + " from array " + hclasses);

        // Return product class
        return new ProductHClass(hclasses);
    }

    @Override
    ProductHClass makeEmptyClass() {
        HClass[] emptyClasses = new HClass[components()];
        for (int i = 0; i < components(); i++) {
            emptyClasses[i] = hierarchies[i].emptyClass();
        }
        return new ProductHClass(emptyClasses, Integer.MAX_VALUE);
    }

    @Override
    ProductHClass makeTopClass() {
        HClass[] topClasses = new HClass[components()];
        for (int i = 0; i < components(); i++) {
            topClasses[i] = hierarchies[i].topClass();
        }
        return new ProductHClass(topClasses, 0);
    }

    private static <H extends HClass> String componentClassName(Hierarchy<H> subhierarchy, ProductHClass hclass, int component) {
        return subhierarchy.className(hclass.component(subhierarchy.hclassType(), component));
    }

    @Override
    public String className(ProductHClass hclass) {
        StringBuilder s = new StringBuilder();
        String separator = "";
        for (int i = 0; i < components(); ++i) {
            s.append(separator);
            s.append(componentClassName(hierarchies[i], hclass, i));
            separator = PRODUCTSEPARATOR;
        }
        return s.toString();
    }

    @Override
    public ProductHClass intersectionBinary(ProductHClass hclass1, ProductHClass hclass2) {
        // Compute componentwise intersection
        HClass[] intsct = new HClass[components()];
        boolean isTop = true;
        for (int i = 0; i < components(); ++i) {
            Class<? extends HClass> componentType = componentType(i);
            HClass hc1 = hclass1.component(componentType, i);
            HClass hc2 = hclass2.component(componentType, i);
            intsct[i] = hierarchies[i].intersection(hc1, hc2);

            // Check whether intersection is empty
            if (intsct[i].equals(hierarchies[i].emptyClass()))
                return emptyClass();

            // Check whether intersection equals top class
            if (isTop && ! intsct[i].equals(hierarchies[i].topClass()))
                isTop = false;
        }

        // Return intersection or top class if appropriate
        return isTop ? topClass() : makeClass(intsct);
    }

    @Override
    //@SuppressWarnings("unchecked")
    public ProductHClass dataClass(HierarchyView<ProductHClass> view, Dataset dataset, int id) {
        HClass[] hclasses = new HClass[components()];
        for (int i = 0; i < components(); ++i) {
            hclasses[i] = _dataClassForComponent(componentType(i), i, view, dataset, id);
        }
        return new ProductHClass(hclasses);
    }

    private <H extends HClass> H _dataClassForComponent(Class<H> hclassType,
            int component, HierarchyView<ProductHClass> view, Dataset dataset, int id) {
        return componentHierarchy(hclassType, component).dataClass(
                view.subview(hclassType, component), dataset, id);
    }


    private static <H extends HClass> Classification<H> _classifyComponent(
            int component, Class<H> hclassType, HierarchyView<ProductHClass> view, Dataset dataset, ProductHClass root) {
        HierarchyView<H> subview = view.subview(hclassType, component);
        Hierarchy<H> hierarchy = subview.hierarchy();
        return hierarchy.classify(root.component(hclassType, component),subview, dataset);
    }

    @Override
    public Classification<ProductHClass> classify(ProductHClass root, HierarchyView<ProductHClass> view,
            Dataset dataset) {
        // Classify each component separately first and order subhierarchies
        Classification<?>[] classifications = new Classification[components()];
        for (int i = 0; i < components(); ++i) {
            classifications[i] =
                _classifyComponent(i, componentType(i), view, dataset, root);
        }
        int[] componentOrdering = componentOrdering(classifications);

        // Now produce a joint classification from the component classifications
        Classification<ProductHClass> classification =
                new ClassificationEngine<ProductHClass>(storageAbstractFactory, this, root);

        // Copy root class to new product class
        HClass[] vector = new HClass[components()];
        for (int i = 0; i < components(); ++i)
            vector[i] = root.hclass(i);
        classification.addClass(root, dataset);
        int firstComponent = componentOrdering[0];
        classifyComponentsRecursively(view, classifications, componentOrdering,
                vector, componentType(firstComponent),
                null, 0, 0, classification, root, level(root));

        // Return classification
        classification.trim();
        return classification;
    }

    int minLevel(int component) {
        return minLevels[component];
    }

    int maxLevel(int component) {
        return maxLevels[component];
    }

    int level(ProductHClass hclass) {
        int level = 0;
        for (int i = 0; i < components(); ++i) {
            level = Math.max(level, _componentLevel(componentType(i), hclass, i));
        }
        return level;
    }

    <H extends HClass> int _componentLevel(Class<H> hclassType, ProductHClass hclass, int component) {
        H componentClass = hclass.component(hclassType, component);
        Hierarchy<H> componentHierarchy = subhierarchy(hclassType, component);
        return componentHierarchy.isTop(componentClass) ? 0 : minLevel(component);
    }

    /**
     * 
     * @param classifications
     * @return
     */
    protected ComponentOrdering componentOrdering() {
        // Specify ordering of subhierarchies: default=in original order
        return new ComponentOrderingList(hierarchies.length);
    }

    protected int[] componentOrdering(Classification<?>[] classifications) {
        return componentOrdering();
    }

    // Determine whether the current vector prefix should be pruned away in the search
    // for classifications
    protected boolean pruneClassifyComponentsRecursively(
            Classification<ProductHClass> classification,
            HClass[] vector,
            int componentIndex,
            int depth,
            int datasetSize) {
        return classification.isBelowDepthThreshold(depth)
                || classification.isBelowSizeThreshold(datasetSize);
    }

    /**
     * Recursively add subclasses to classified data set based on the coordinatewise classifications
     * @param <H> the hierarchy class type associated with the current component
     * @param view the view that provides access to the data set
     * @param classifications the classifications for the individual components
     * @param dataset the data points that are contained in hclasses so far (<code>null</code>
     *     if all data points have survived)
     * @param hclassType  the runtime type of the classes in the component
     * @param vector the current vector of classes
     * @param componentOrdering the order in which components are processed
     * @param componentIndex the index of the current component
     * @param depth the relative depth of the current hclasses prefix
     * @param classification the classification in which the results must be stored
     */
    @SuppressWarnings("unchecked")
    <H extends HClass> void classifyComponentsRecursively(
            HierarchyView<ProductHClass> view, Classification<?>[] classifications,
            int[] componentOrdering, HClass[] vector,
            Class<H> hclassType,
            Dataset dataset,
            int componentIndex, int depth,
            Classification<ProductHClass> classification, ProductHClass root, int level) {
        // Prune classifications if the vector is too deep, or the data set is too small
        if (pruneClassifyComponentsRecursively(classification, vector, componentIndex, depth, dataset.size()))
            return;
        
        // Find next component to process and store current component class
        int component = componentOrdering[componentIndex];
        int componentLevel = minLevels[component];
        int newlevel = Math.max(level, componentLevel);
        HClass oldComponentClass = vector[component];
        Classification<H> componentClassification =
                (Classification<H>) classifications[component];

        // First attempt to use the top class for this component
        if (componentIndex + 1 == components()) {
            // This is the last component: add vector to classification if possible
            if (depth > 0 && dataset != null)
                classification.addClass(makeClass(vector), dataset);
        } else {
            // Not the last component: continue recursively with remaining components
            classifyComponentsRecursively(view,
                classifications, componentOrdering,
                vector, componentType(componentOrdering[componentIndex+1]),
                dataset, componentIndex + 1, depth, classification, root, newlevel);
        }

        // Then iterate through all possible classifications for component within maxDepth
        if (componentLevel >= level) {
            int maxComponentDepth = Math.max(0, classification.parameters().maximalClassDepth()-depth);
            for (int componentDepth = 1; componentDepth < maxComponentDepth; ++componentDepth) {
                // Iterate through all possible classifications at the given component depth
                List<H> componentHclasses = componentClassification.classes(componentDepth);
                Collections.sort(componentHclasses, componentClassification.sizeComparator());
                for (H componentHclass : componentHclasses) {
                    // Set current component hclass
                    vector[component] = componentHclass;

                    // Intersect old dataset with dataset for current component
                    Dataset componentDataset = componentClassification.dataset(componentHclass);
                    componentDataset = dataset == null
                            ? componentDataset
                            : dataset.intersection(componentDataset);

                    // Recursively classify next component, or save classification if
                    // no more components
                    if (componentIndex + 1 == components()) {
                        // Last component
                        if (depth > 0 && componentDataset != null)
                            classification.addClass(makeClass(vector), dataset);
                    } else {
                        classifyComponentsRecursively(view,
                            classifications, componentOrdering,
                            vector, componentType(componentOrdering[componentIndex+1]),
                            componentDataset, componentIndex + 1, depth + componentDepth,
                            classification, root, newlevel);

                    }
                }
            }
        }

        // Reset component hclass (not strictly necessary, but probably nice for debugging)
        vector[component] = oldComponentClass;
    }


    @Override
    public boolean contains(ProductHClass hclass, HierarchyView<ProductHClass> view,
            Dataset dataset, int identifier) {
        // Check that each component contains datapoint
        for (int i = 0; i < components(); ++i) {
            if (! _containsInComponent(i, subhierarchy(identifier), hclass, view, dataset, identifier))
                return false;
        }
        return true;
    }

    private <H extends HClass> boolean _containsInComponent(int component, Hierarchy<H> subhierarchy,
            ProductHClass hclass, HierarchyView<ProductHClass> view, Dataset dataset, int identifier) {
        Class<H> hclassType = subhierarchy.hclassType();
        HierarchyView<H> subview = view.subview(hclassType, component);
        H component = hclass.component(hclassType, component);
        return subhierarchy.contains(component, subview, dataset, identifier);
    }

    @SuppressWarnings("unchecked")
    public <H extends HClass> Hierarchy<H> componentHierarchy(Class<H> hclassType, int component) {
        Hierarchy<?> subhierarchy = subhierarchy(component);
        if (subhierarchy.hclassType().equals(hclassType))
            return (Hierarchy<H>) subhierarchy;
        else
            throw new IllegalArgumentException("Subhierarchy "
                    + component + " in hierarchy " + this + ": expected hclass type "
                    + hclassType + " but found " + subhierarchy.hclassType());
    }

    public Class<? extends HClass> componentType(int component) {
        return subhierarchy(component).hclassType();
    }

    private <H extends HClass> HClass _componentClass(
            Hierarchy<H> subhierarchy, ProductHClass hclass, int component, int dimension) {
        return subhierarchy.componentClass(
                hclass.component(subhierarchy.hclassType(), component), dimension);
    }

    @Override
    public HClass componentClass(ProductHClass hclass, int dimension) throws IllegalArgumentException {
        // Check validity of dimension
        if (dimension < 0 || dimension >= dimensions())
            throw new IllegalArgumentException("Illegal dimension: must be within range [0," + dimensions()
                    + "[, but was " + dimension);

        // Identify the correct component
        int offset = 0;
        for (int component = 0; component < components(); ++component) {
            offset += hierarchies[component].dimensions();
            if (offset > dimension) {
                offset -= hierarchies[component].dimensions();
                Class<? extends HClass> hclassType = hierarchies[component].hclassType();
                return _componentClass(subhierarchy(component),
                        hclass, component, dimension - offset);
            }
        }

        // Throw exception
        throw new IndexOutOfBoundsException("Failed to identify component containing dimension " + dimension);
    }

    private <H extends HClass> HClass _componentClassAtDepth(
            Hierarchy<H> subhierarchy, ProductHClass hclass, int component, int dimension, int depth) {
        return subhierarchy.componentClassAtDepth(
                hclass.component(subhierarchy.hclassType(), component), dimension, depth);
    }

    @Override
    public HClass componentClassAtDepth(ProductHClass hclass, int dimension, int depth) throws IllegalArgumentException {
        // Check validity of dimension
        if (dimension < 0 || dimension >= dimensions())
            throw new IllegalArgumentException("Illegal dimension: must be within range [0," + dimensions()
                    + "[, but was " + dimension);

        // Identify the correct component
        int offset = 0;
        for (int component = 0; component < components(); ++component) {
            offset += hierarchies[component].dimensions();
            if (offset > dimension) {
                offset -= hierarchies[component].dimensions();
                return _componentClassAtDepth(subhierarchy(component),
                        hclass, component, dimension - offset, depth);
            }
        }

        // Throw exception
        throw new IndexOutOfBoundsException("Failed to identify component containing dimension " + dimension);
    }

    private <H extends HClass> int[] _subclassComponents(Hierarchy<H> subhierarchy,
            ProductHClass hclass, ProductHClass subclass, int offset, int component) {
        Class<H> hclassType = subhierarchy.hclassType();
        return subhierarchy.subclassComponents(hclass.component(hclassType, component),
                subclass.component(hclassType, component), offset);
    }

    @Override
    public int[] subclassComponents(final ProductHClass hclass, final ProductHClass subclass, final int offset) {
        int subclassDimensionCount = 0;

        // Collect subclass dimensions from components
        int[] subclassDimensions = new int[dimensions()];
        int componentOffset = offset;
        for (int component = 0; component < components(); ++component) {
            Hierarchy<?> subhierarchy = subhierarchy(component);
            int[] componentDimensions = _subclassComponents(subhierarchy, hclass, subclass, componentOffset, component);
            for (int i = 0; i < componentDimensions.length; ++i) {
                subclassDimensions[subclassDimensionCount++] = componentDimensions[i];
            }
            componentOffset += subhierarchy.dimensions();
        }

        // Create final array
        return Arrays.copyOf(subclassDimensions, subclassDimensionCount);
    }

    <H extends HClass> HierarchyIterator<H> _componentIterator(
            Hierarchy<H> subhierarchy, ProductHClass root, ProductHClass hclass, int component) {
        return subhierarchy.hierarchyIterator(
                root.component(subhierarchy.hclassType(), component),
                hclass.component(subhierarchy.hclassType(), component));
    }

    public HierarchyIterator<?> componentIterator(ProductHClass root, ProductHClass hclass, int component) {
        return _componentIterator(subhierarchy(component), root, hclass, component);
    }

    @Override
    public Collection<ProductHClass> superclasses(ProductHClass hclass) {
        return superclassesBelowRoot(hclass, topClass(), 0, hclass.depth());
    }

    @Override
    public List<ProductHClass> superclassesBelowRoot(ProductHClass hclass,
            ProductHClass root, int minDepthBelowRoot, int maxDepthBelowRoot) {
        ArrayList<ProductHClass> list = new ArrayList<ProductHClass>();
        _superclassesBelowRoot(hclass, root, minDepthBelowRoot, maxDepthBelowRoot, 0, list);
        list.trimToSize();
        return Collections.unmodifiableList(list);
    }
}